//
// Created by Javery Chiang on 2025/5/4.
//

#include "Page.h"


/**
 * 先进先出
 * @param pages ：系统调用页号顺序
 * @param cap ：cap内存最大容量
 * @return
 */
int FIFO(const vector<int> &pages, int cap) {
    queue<int> pageQueue;
    // 记录页面是否已在内存中
    unordered_set<int> pageSet;

    // 缺页计数
    int pageFaults = 0;
    for (int page: pages) {
        // 查找当前页是否存在内存中
        if (pageSet.find(page) != pageSet.end()) {
            continue;
        }
        pageFaults++;
        // 栈页面已满，缺页需要弹出第一个页面
        if (pageQueue.size() == cap) {
            // 取出第一个页面（头元素指针，不弹出）
            int oldst = pageQueue.front();
            // 弹出第一个页面，无引用指针
            pageQueue.pop();
            // 清除页面内存记录
            pageSet.erase(oldst);
        }
        pageSet.insert(page);
        pageQueue.push(page);
    }

    return pageFaults;
}

/**
 * 最近最少使用
 * @param pages ：系统调用页号顺序
 * @param cap ：cap内存最大容量
 * @return
 */
int LRU(const vector<int> &pages, int cap) {
    // 记录存储页面和最近使用的时间戳
    unordered_map<int, int> pageMap;
    // 记录内存中存在的页面
    unordered_set<int> pageSet;
    int time = 0;
    int pageFaults = 0;

    for (int page: pages) {
        time++;
        // 页面在内存中更新最新使用时间
        if (pageSet.find(page) != pageSet.end()) {
            pageMap[page] = time;
            continue;
        }
        // 缺页计数
        pageFaults++;

        // 内存已满
        if (pageSet.size() == cap) {
            // 最近最少使用页号
            int lruPage = -1;
            int minTime = INT_MAX;

            for (auto it = pageSet.begin(); it != pageSet.end(); ++it) {
                if (pageMap[*it] < minTime) {
                    minTime = pageMap[*it];
                    lruPage = *it;
                }
            }
            pageSet.erase(lruPage);
            pageMap.erase(lruPage);
        }

        pageSet.insert(page);
        pageMap[page] = time;
    }
    return pageFaults;
}

/**
 * 未来最长时间不被使用,最佳置换算法
 * @param pages ：系统调用页号顺序
 * @param cap ：cap内存最大容量
 * @return
 */
int OPT(const vector<int> &pages, int cap) {
    unordered_set<int> pageSet;
    int pageFaults = 0;

    for (int i = 0; i < pages.size(); ++i) {
        // 页面在内存中
        if (pageSet.find(pages[i]) != pageSet.end()) {
            continue;
        }
        pageFaults++;
        // 页存已满
        if (pageSet.size() == cap) {
            // farthest：最晚标识，replace替换页面
            int farthest = -1, replacePage = -1;
            // 从当前内存页比较未来出现的页号
            for (auto it = pageSet.begin(); it != pageSet.end(); ++it) {
                //后一个循环序号
                int j;
                for (j = i + 1; j < pages.size(); j++) {
                    // 后一个使用页面已在内存中
                    if (pages[j] == *it) {
                        break;
                    }
                }
                // 后续出现序号 pages[i+1, end] 不再出现本次内存中，则直接替换当前内存
                if (j == pages.size()) {
                    replacePage = *it;
                    break;
                }
                // 后续出现序号 pages[i+1, end] 都出现在本次内存中，则通过farthest记录最后出现的下表
                if (j > farthest) {
                    farthest = j;
                    replacePage = *it;
                }
            }
            pageSet.erase(replacePage);
        }
        pageSet.insert(pages[i]);
    }
    return pageFaults;

}


void FIFO_PRINT(const vector<int> &pages, int frames){
    std::queue<int> q; // 存储当前内存中的页面（按进入顺序）
    std::unordered_set<int> in_memory; // 快速判断页面是否在内存
    int page_faults = 0;

    std::cout << "FIFO 页面置换过程（帧数=" << frames << "）:\n";

    for (int page : pages) {
        std::cout << "访问页面 " << page << ": ";

        // 页面已在内存中
        if (in_memory.find(page) != in_memory.end()) {
            std::cout << "命中\n";
            continue;
        }

        // 页面缺页，需替换
        page_faults++;
        if (q.size() == frames) {
            int oldest = q.front();
            q.pop();
            in_memory.erase(oldest);
            std::cout << "替换 " << oldest << " → ";
        }

        // 加载新页面
        q.push(page);
        in_memory.insert(page);
        std::cout << "加载 → 当前内存: [";
        for (int p : in_memory) std::cout << p << " ";
        std::cout << "]\n";
    }
    std::cout << "总缺页次数: " << page_faults << "\n\n";
}